package com.leecode.exercise;

public class 最大公共子串 {

    public static void main(String[] args) {
        String a = "abjkl";
        String b = "absjkl";
        String maxLenComStr = comSubStr(a, b);
        System.out.println("查找两个字符串a,b中的最长公共子串: " + maxLenComStr);
    }

    public static String comSubStr(String a, String b) {

        int lenA = a.length();
        int lenB = b.length();

        int[][] dp = new int[lenA + 1][lenB + 1];

        int maxLen = 0;
        int end = 0;

        // 填充动态规划数组
        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                // 如果当前字符相等
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    // 在之前的最长公共子串长度基础上加1
                    dp[i][j] = dp[i - 1][j - 1] + 1;

                    // 如果新的子串长度更长，则更新最大长度和结束位置
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        end = i; // 记录最长公共子串的结束位置
                    }
                } else {
                    // 如果当前字符不相等，则子串长度重置为0
                    dp[i][j] = 0;
                }
            }
        }

        String mxLenStr = a.substring(end - maxLen, end);
        return mxLenStr;
    }
}
